﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphLab
{
    class Graph
    {
        List<Node> nodes;
        List<Edge> edges;
        
        public List<Node> Nodes { get { return nodes;} }
        public List<Edge> Edges { get { return edges; } }

        public Graph()
        {
            nodes = new();
            edges = new();
        }

        bool containsNode(string name)
        {
            foreach (var node in nodes)
                if (node.Name == name)
                    return true;
            return false;
        }

        public bool makeNode(string name)
        {
            if (!containsNode(name))
            {
                var node = new Node(name);
                nodes.Add(node);
                return true;
            }
            else
                return false;
        }


        Node findNode(string name)
        {
            foreach (var node in nodes)
                if (node.Name == name)
                    return node;
            return null;
        }

        public void addEdge(string from, string to, int weight)
        {
            if (weight <= 0) throw new Node.NodeEx("Weight must be more than zero");

            var fromNode = findNode(from);
            if (fromNode == null) throw new Node.NodeEx("Begin node doesn't exist");

            var toNode = findNode(to);
            if (toNode == null) throw new Node.NodeEx("End node doesn't exist");

            var edge = new Edge(weight, fromNode, toNode);
            fromNode.addEdge(edge);
            edges.Add(edge);
        }

        public List<Edge> findMinTree()
        {
            nodes[0].IsVisited = true;
            var res = new List<Edge>();
            int minWeight;
            Edge minEdge;

            while (res.Count < nodes.Count - 1)
            {
                minWeight = 1000;
                minEdge = null;

                foreach (var edge in edges)
                {
                    if (edge.BNode.IsVisited == true && edge.ENode.IsVisited == false && edge.Weight < minWeight)
                    {
                        minWeight = edge.Weight;
                        minEdge = edge;
                    }
                }
                if (minEdge != null)
                {
                    res.Add(minEdge);
                    minEdge.ENode.IsVisited = true;
                }
            }
            return res;
        }
    }

    class Node
    {
        public class NodeEx : Exception
        {
            string? message;
            string? Message { get { return message; } }

            public NodeEx(string? message)
            {
                this.message = message;
            }

        }

        string name;
        bool isVisited;
        List<Edge> edges;
        public List<Edge> Edges { get { return edges; } }

        public string Name { get { return name; } }

        public bool IsVisited { get { return isVisited; } set { isVisited = value; } }

        public Node(string name) 
        { 
            this.name = name;
            edges = new List<Edge>();
            isVisited = false;
        }


        public void addEdge(Edge edge) { edges.Add(edge); }
    }

    class Edge
    {
        int weight;
        Node bNode;
        Node eNode;

        public Node BNode { get { return bNode; } }
        public Node ENode { get { return eNode; } }

        public int Weight { get { return weight; } }

        public Edge(int weight, Node bNode, Node eNode)
        {
            this.weight = weight;
            this.bNode = bNode;
            this.eNode = eNode;
        }

    }
}